const arr = [2, 4, 1, 7, 3, 1, 6, 5]

// 最优解，最优时间O(n)，普遍O(n^2)
// function bubble_sort(arr) {
//   const len = arr.length
//   for (var i = 0; i < len; i++) {
//     let flag = true
//     for (var j = 0; j < len - 1 - i; j++) {
//       if (arr[j] > arr[j + 1]) {
//         [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
//         flag = false
//       }
//     }
//     if (!flag) return arr
//   }
//   return arr
// }


// function bubble_sort(arr) {
//   for (let i = 0; i < arr.length; i++) {
//     for (let j = i + 1; j < arr.length; j++) {
//       if (arr[j] < arr[i]) {
//         [arr[j], arr[i]] = [arr[i], arr[j]]
//       }
//     }
//   }
//   return arr
// }




// 下面代码有问题
// function bubble(arr) {
//   for (let i = 0; i < arr.length; i++) {
//     let min = getMin(arr.slice(i), i)
//     let minIndex = arr.indexOf(min)
//     console.log(minIndex);
    
//     let flag = arr[i]
//     arr[i] = arr[minIndex]
//     arr[minIndex] = flag

//     // [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
//   }
//   return arr
// }

// function getMin(arr, k) {
//   let min = arr[k]
//   for (let j = k; j < arr.length; j++) {
//     if (arr[j] < min) {
//       min = arr[j]
//     }
//   }
//   return min
// }

console.log(bubble(arr));
